package leetcode.code0044;

public class Solution extends Solution44 {

	@Override
	public boolean isMatch(String s, String p) {
		// s 可能为空，且只包含从 a-z 的小写字母。
		// p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。
		if (s == null || p == null) {
			return false;
		}
		int lens = s.length();
		int lenp = p.length();
		boolean[][] ans = new boolean[lens + 1][lenp + 1];
		ans[0][0] = true;
		for (int i = 1; i <= lens; i++) {
			ans[i][0] = false;
		}
		for (int i = 1; i <= lenp; i++) {
			ans[0][i] = p.charAt(i - 1) == '*' ? ans[0][i - 1] : false;
		}
		for (int i = 1; i <= lens; i++) {
			for (int j = 1; j <= lenp; j++) {
				if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?') {
					ans[i][j] = ans[i - 1][j - 1];// 当前字符匹配,当前s[0..i-1]p[0..j-1]是否匹配取决于之前ans[i - 1][j - 1]
				} else {
					// 当前字符不匹配
					if (p.charAt(j - 1) == '*') {
						// p串当前是*
						// ans[i][j - 1]匹配,*当无用
						// ans[i - 1][j - 1],*当s[i-1]字符用
						// ans[i - 1][j],*当匹配字符串用,相当于s[i-1]位置字符追加到之前的字符串里同*匹配
						if (ans[i][j - 1] || ans[i - 1][j - 1] || ans[i - 1][j]) {
							ans[i][j] = true;
						}
					}
//					else if (p.charAt(j - 1) == '?') { // 合并到上边的条件
//						ans[i][j] = ans[i - 1][j - 1];
//					}
					else {
						ans[i][j] = false;
					}
				}

			}
		}
		return ans[lens][lenp];
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();
	}

}
